Konveksni omotač
Obujmice
Dosad prikazane metode omogućuju nam da napravimo simulaciju dinamike čvrstih tijela visokog stupnja realističnosti. Problemi će nastati kada u scenu stavimo više objekata ili kada mreže poligona kojima su definirani objekti postanu detaljnije. U oba slučaja doći će do povećanja ukupnog broja poligona u sceni. Pošto se naša rutina za detekciju sudara oslanja na detekciju sudara dvaju trokuta, povećanje broja poligona dovesti će do pada performansi simulacije. Da bismo to spriječili, moramo smanjiti broj trokuta koji se provjeravaju radi sudara. Dva su načina na koji to možemo učiniti, pojednostavljenjem reprezentacije objekta ili smanjenjem dijelova mreže trokuta koje ćemo testirati radi sudara.
Način da drastično smanjimo broj testova primitiva je da mrežu poligona koja predstavlja neki objekt zamijenimo sa jednom primitivom ili pak manjim brojem primitiva. Ovakve reprezentacije objekta nazivamo obujmicama jer u potpunosti obujmljuju originalni objekt.
a) Obujmica oblika kvadra. b) Obujmica oblika sfere. c) Konveksni omotač.
Upotreba konveksnog omotača
Pošto je u primjeni obujmica jako važno dobro prianjanje obujmice, posebnu ćemo pozornost posvetiti korištenju konveksnog omotača pri detekciji sudara dvaju objekata. Konveksni omotač nekog objekta je najmanje, konveksno geometrijsko tijelo koje može obuhvatiti taj objekt. Ukoliko je sam objekt konveksan, njegova mreža poligona je njegov konveksni omotač.
Inkrementalni algoritam
Definiramo skup točaka za koji radimo konveksni omotač V , skup trokuta konveksnog omotača T te skup bridova konveksnog omotača E. Također definiramo skup vidljivih bridova Ev.
Izgradnju konveksnog omotača započinjemo izradom d-trokuta. Za d-trokut nam trebaju tri nekolinearne točke. Uzimamo prve tri nekolinearne točke iz skupa točaka V . Nakon što smo napravili d-trokut, dodajmo njegova tri brida u skup E i njegova dva trokuta u skup T. Ovaj d-trokut je naš privremeni konveksni omotač koji ćemo unaprjeđivati sa svakom novom točkom iz skupa V u glavnoj petlji.
Glavna petlja inkrementalnog algoritma
//Za svaku novu točku Vi
ZA svaki trokut Ti iz skupa trokuta konveksnog omotača T
AKO ( Vi vidi Ti )
ZA svaki brid Ei trokuta Ti
AKO ( Ei nije u skupu vidljivih bridova ) dodaj Ei u skup vidljivih bridova EV
INAČE ( obriši brid Ei iz skupa vidljivih bridova EV )
obriši trokut Ti iz skupa trokuta konveksnog omotača T
AKO (skup vidljivih bridova EV nije prazan)
ZA svaki brid EV iiz skupa vidljivih bridova EV
napravi novi trokut Tv
dodaj trokut Tv u skup trokuta konveksnog omotača T
obriši brid EV iiz skupa vidljivih bridova EV